#include<bits/stdc++.h>
// debuging!!!
/**
 * @brief 树上差分抽象基类
 * @note 采用模板方法模式定义算法骨架
 */
class LCATree {
public:
    using i64 = long long;
protected:
    int n, root;
    std::vector<std::vector<int>> adj, parent;
    std::vector<int> depth;
    std::vector<i64> diff;
    
    static const int max_high = 20;

    void dfsLca(int u, int fa) {
        depth[u] = depth[fa] + 1;
        parent[u][0] = fa;
        for(int i = 1; i <= max_high; i++) {
            parent[u][i] = parent[parent[u][i - 1]][i - 1];
        }
        for(auto v : adj[u]) {
            if(v == fa) {
                continue;
            }
            dfsLca(v, u);
        }
    }

    int lca(int a, int b) const {
        if(depth[a] < depth[b]) {
            std::swap(a, b);
        }
        for(int i = max_high; i >= 0; i--) {
            if(depth[parent[a][i]] >= depth[b]) {
                a = parent[a][i];
            }
        }
        if(a == b) {
            return a;
        }
        for(int i = max_high; i >= 0; i--) {
            if(parent[a][i] != parent[b][i]) {
                a = parent[a][i];
                b = parent[b][i];
            }
        }
        return parent[a][0];
    }

public:
    explicit LCATree(int _n, int _root = 0) 
    : n(_n),
      root(_root)
    {
        adj.assign(n, {});
        parent.resize(n, std::vector<int>(max_high + 1, 0));
        depth.resize(n, 0);
        diff.resize(n, 0);
    }

    virtual ~LCATree() = default;

    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    void prepareLca(int _root = 0) {
        this->root = _root;
        depth[this->root] = 0;  
        dfsLca(root, root);
    }

    virtual void applyparentdate(int u, int v, i64 val) = 0;
    virtual void calculateResult() = 0;

    i64 getAns(int u) const {
        return diff[u];
    }
    
};


/**
 * @brief 边差分实现
 * @note 边权存储在下级节点
 */
class EdgeDifference : public LCATree {
public:
    using LCATree::LCATree;

    void applyparentdate(int u, int v, i64 val) override {
        const int ancester = lca(u, v);
        diff[u] += val;
        diff[v] += val;
        diff[ancester] -= 2LL * val;
    }

    void calculateResult() override {
        postOrderCalculate(root, root);
    }
private:
    void postOrderCalculate(int u, int fa) {
        for(auto v : adj[u]) {
            if(v == fa) {
                continue;
            }
            postOrderCalculate(v, u);
            diff[u] += diff[v];
        }
    }
};

int main() {

    try {
        constexpr int n = 6;  // 节点编号1-6
        constexpr int root = 0;

        // 边差分测试
        {
            EdgeDifference edgeDiff(n, root);
            edgeDiff.addEdge(0, 1);
            edgeDiff.addEdge(0, 2);
            edgeDiff.addEdge(1, 3);
            edgeDiff.addEdge(1, 4);
            edgeDiff.addEdge(2, 5);
            edgeDiff.prepareLca();

            edgeDiff.applyparentdate(3, 5, 2);  // 路径4-2-1-3-6
            edgeDiff.calculateResult();

            std::cout << "\n边差分结果:\n";
            
        }
    } catch (const std::exception& e) {
        std::cerr << "Error: " << e.what() << std::endl;
        return 1;
    }

    return 0;
}